# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 6_bubble_sort.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2021/12/30 15:24
------------------------------------------
    冒泡排序，这里以从小到大的顺序排序
"""


def bubble_sort_v1(array):
    """
        冒泡排序基础版
    """
    for i in range(len(array) - 1):
        for j in range(len(array) - 1 - i):
            temp = array[j]
            if temp > array[j + 1]:
                array[j] = array[j + 1]
                array[j + 1] = temp


def bubble_sort_v2(array):
    """
        对数列进行所有轮次排序之前，数列已经有序的情况进行考虑，优化排序
    """
    for i in range(len(array) - 1):
        # 是否有序的标记，每一轮默认有序，只要该轮排序中进行过数值交换，则数列进行下一轮排序之前不一定有序，则改为False
        is_sorted = True
        for j in range(len(array) - 1 - i):
            temp = array[j]
            if temp > array[j + 1]:
                array[j] = array[j + 1]
                array[j + 1] = temp
                is_sorted = False

        if is_sorted:
            break


def bubble_sort_v3(array):
    """
       对数组排序前，数组尾部已经部分有序的情况进行优化: 添加标记变量，记录下最后一次元素交换时的位置，该位置即为无序区的边界
       demo: [3, 4, 2, 1, 5, 6, 7, 8]
    """
    # 最后一次交换的位置，即交换前，索引小的元素的索引值
    last_exchange_index = len(array)

    # 无序区边界，也就是无序区最后一个元素位置, 每次比较，只需要比较到这里即可
    sort_border = len(array) - 1

    for i in range(len(array) - 1):
        # 是否有序的标记，每一轮默认有序，只要该轮排序中进行过数值交换，则数列进行下一轮排序之前不一定有序，则改为False
        is_sorted = True
        for j in range(sort_border):
            temp = array[j]
            if temp > array[j + 1]:
                array[j] = array[j + 1]
                array[j + 1] = temp
                is_sorted = False

                last_exchange_index = j

        sort_border = last_exchange_index

        if is_sorted:
            break


def cock_tail_sort(array):
    """
        鸡尾酒排序，基础版
    """
    array_len = len(array)

    for i in range(array_len // 2):

        # 是否有序的标记，每一轮的初始值都是True
        is_sorted = True

        # 奇数轮，从左向右比较和交换
        for j in range(i, array_len - i - 1):
            if array[j] > array[j + 1]:
                temp = array[j]
                array[j] = array[j + 1]
                array[j + 1] = temp

                # 有元素交换，所以不是有序的，标记为False
                is_sorted = False

        if is_sorted:
            break

        # 偶数轮，先将有序状态重新标为 True
        is_sorted = True
        for k in range(array_len - i - 1, i, -1):
            if array[k] < array[k - 1]:
                temp = array[k]
                array[k] = array[k - 1]
                array[k - 1] = temp

                # 有元素交换，所以不是有序的，标记为False
                is_sorted = False

        if is_sorted:
            break


def demo():
    lis = [1, 3, 2, 4, 9, 5, 8, 0, 7, 6]
    lis2 = [3, 4, 2, 1, 5, 6, 7, 8]
    print(f"原始数组: {lis2}")
    bubble_sort_v3(lis2)
    print(f"冒泡排序后： {lis2}")

    lis3 = [3, 4, 14, 1, 5, 6, 7, 8, 1, -1, 0, 9, 11]
    print(f"鸡尾酒排序前：{lis3}")
    cock_tail_sort(lis3)
    print(f"鸡尾酒排序后：{lis3}")

    # out: [-1, 0, 1, 1, 3, 4, 5, 6, 7, 8, 9, 11, 14]


if __name__ == '__main__':
    demo()
